package dongtai;

public class MinCostToTransform {
    public static void main(String[] args) {
        int target = 2024;
        int result = minCostToTransform(target);
        System.out.println("将整数从 1 变为 2024 的最小代价是: " + result);
    }

    public static int minCostToTransform(int target) {
        int[] dp = new int[target + 1];
        dp[1] = 0;

        for (int i = 2; i <= target; i++) {
            int cost1 = dp[i - 1] + 1;
            int maxDigit = maxDigit(i);
            int cost2 = (i - maxDigit >= 1) ? dp[i - maxDigit] + 3 : Integer.MAX_VALUE;
            int cost3 = (i % 2 == 0) ? dp[i / 2] + 10 : Integer.MAX_VALUE;

            dp[i] = Math.min(cost1, Math.min(cost2, cost3));
        }

        return dp[target];
    }

    public static int maxDigit(int num) {
        int maxDigit = 0;
        while (num > 0) {
            int digit = num % 10;
            maxDigit = Math.max(maxDigit, digit);
            num /= 10;
        }
        return maxDigit;
    }
}

